In digital arithmetic, partial products are obtained when two numbers are multiplied together. The number of partial products will depend on the method used for obtaining the partial products. In a conventional operation, the number of partial products may be equal to the number of bits in the multiplier. However, techniques such as Booth encoding make it possible to reduce the number of partial products obtained. For example Booth coding allows the number of partial products to be reduced by a factor of 2. The Booth encoding method is sometimes referred to as the Booth-MacSorley algorithm.
In the Booth coding method, a triplet of bits of the multiplier is input to a Booth coder which provides three outputs, the values of which depends on the input values. The outputs of the Booth coder are then used to modify bits of the number to be multiplied by the multiplier.
Carry save adders which reduce three partial products to two partial products are known. This type of carry save adder is sometimes referred to as a 3 to 2 carry save adder. Such a carry save adder is in fact a full adder. A full adder is a binary logic circuit which produces a two-bit sum where one bit represents the sum and the other bit represents the carry when three one bit binary numbers are added together. The three one bit numbers may be corresponding bits from three partial products.
Carry save adders which reduce four partial products to two partial products are also known. This type of carry save adder is known as a 4 to 2 carry save adder. One example of such a carry save adder is shown in the IEEE Journal of Solid State circuits, Vol 30, No 3, March 1995: “A 4.4 ns CMOS 54×54-b using pass-transistor multiplexer”, page 251 to 257, N Ohkubo et al. This structure generally yields faster partial product compression than the use of 3 to 2 carry save adders. The 4 to 2 carry save adder actually compresses five partial products into three and is therefore sometimes referred to as a 5 to 3 carry save adder. This carry save adder is connected in such a way that four of the inputs are corresponding bits from four partial products whilst the fifth input is fed from a neighbouring adder and is known as the “carry in”. The output of this carry save adder consists of one sum bet and two carry bits. One of these carry bits is input to a neighbouring carry save adder and forms one of the five inputs of that carry save adder.